//
//  STLExample.cpp
//  leetcode
//
//  Created by Ellie on 2021/1/30.
//  Copyright © 2021 Ellie. All rights reserved.
//

#include <stdio.h>
#include "STLExample.h"
#include "BinaryTree.h"
#include "Helper.h"
#include <iostream>
#include <string>

void STLExample::containerExample()
{
    deque<int> de01;
    deque<int> de02{1,2,3};
    
    de01.push_back(100);
    de01.push_back(200);
    de01.push_back(300);
    de01.push_front(1000);
    
    int val = de01.front();
    cout << val << endl;
    
    de01.pop_front();
    de01.pop_back();
    de01.front();
    de01.back();
    
    queue<int> qu;
    // insert element
    qu.push(100);
    // next element
    qu.front();
    // remove next element
    qu.pop();
    // last element
    qu.back();
    if(qu.empty())
    {}
    int qusize = qu.size();
    
    // with 4 element with list
    vector<int> v{1,2,3,4};
    // with 10 element all 0
    vector<int> ve002(10, 0);
    
    // with array
    int arr[] = { 10, 20, 30 };
    int n = sizeof(arr) / sizeof(arr[0]);
    vector<int> vect(arr, arr + n);
    
    // with other vector
    vector<int> vect1{ 10, 20, 30 };
    vector<int> vect2(vect1.begin(), vect1.end());
    
    // with 10 element all 5
    vector<int> vect3(10);
    int value = 5;
    fill(vect3.begin(), vect3.end(), value);
    
    // check if exist or find target with std::find
    if(std::find(vect3.begin(), vect3.end(), 5) != vect3.end())
    {
        cout << "we find 5." << endl;
    }
    else
    {
        cout << "we can't find 5." << endl;
    }
    
    // with copy of vect3
    vector<int> vect4(vect3);
    
    // add element at end
    vect3.push_back(10);
    // delete last element
    vect3.pop_back();
    vect3.resize(10);
    vect3.at(0);
    vect3.clear();
    // 注意迭代器在插入和删除之后失效
    vect3.insert(vect3.begin(), 10);
    // 在数组开始插入3个100
    vect3.insert(vect3.begin(), 3, 100);
    // 删除第[1]元素
    vect3.erase(vect3.begin() + 1);
    // 升序排列
    sort(vect3.begin(), vect3.end());
    // 翻转vector
    reverse(vect3.begin(), vect3.end());
    
    // 2d-array
    int row = 2, column = 5;
    // with 2*5 all 0
    vector<vector<int>> vec2d(row, vector<int> (column, 0));
    vec2d = vector<vector<int>>(row, vector<int>(column, -1));

    stack<int> sk;
    sk.push(100);
    sk.top();
    sk.pop();
    int sksize = sk.size();
    if(sk.empty())
    {
    }
    
    val = de01.front();
    cout << val << endl;
    val = de01.back();
    cout << val << endl;
    
    Printf_deque("deque01", de01);
    Printf_deque("deque02", de02);
    
    unordered_map<string, string> hashmap;
    hashmap["Bakery"]="Barbara";  // new element inserted
    hashmap["Seafood"]="Lisa";    // new element inserted
    hashmap["Produce"]="John";    // new element inserted
    
    // check if Key:Produce Exist
    if(hashmap.find("Produce") != hashmap.end())
    {
    }
    // check if key count > 0
    if(hashmap.count("Produce"))
    {
    }
    
    std::string name = hashmap["Bakery"];   // existing element accessed (read)
    hashmap["Seafood"] = name;              // existing element accessed (written)

    hashmap["Bakery"] = hashmap["Produce"];   // existing elements accessed (read/written)

    name = hashmap["Deli"];      // non-existing element: new element "Deli" inserted! value ""

    hashmap["Produce"] = hashmap["Gifts"];    // new element "Gifts" inserted, "Produce" written to ""

    for (auto& x: hashmap) {
        std::cout << x.first << ": " << x.second << std::endl;
    }
    
    vector<int> vectforset{1,22,3};
    // 去重复set哈希集合
    unordered_set<int> sets(vectforset.begin(), vectforset.end());
    
    
    // 小顶堆，每次取堆的元素都为当前堆的最小值
    priority_queue<ListNode*, vector<ListNode*>, compareNode> que;
    
    // push all lists head to priority_queue
    // 优先级队列
    vector<ListNode*> lists;
    for(auto l : lists)
    {
        if(l != nullptr)
            que.push(l);
    }
    
    // use priority_queue<int> less; 大顶堆
    // 删除K - 1个元素，que当前的top就是第K大的元素
    vector<int> nums{2,4,5,66,7,7,8,45,45,34,109,120,125,135,145};
    priority_queue<int> bigheap(nums.begin(), nums.end());
    int size = nums.size();
    int K = 3;
    while(K-- > 1)
    {
        bigheap.pop();
    }
    int topkvalue = bigheap.top();
    
    priority_queue<int> emptyqueue;
    // less比较函数 大顶堆，top is current biggest num
    priority_queue<int> firstqueue(nums.begin(), nums.begin() + 4);
    // greater比较函数，小顶堆，top is current smallest num
    priority_queue<int, vector<int>, greater<int>> second(nums.begin(), nums.end());
    

    // C++ list STL
    // std::list
    // Lists are sequence containers that allow constant time insert and erase operations anywhere within the sequence, and iteration in both directions.
    // List containers are implemented as doubly-linked lists;
    // C++中的list采用双向链表实现，常数时间复杂度删除和插入元素
    // Double Link-list
    std::list<int> list02(nums.begin(), nums.end());
    printstdlist("std::list", list02);
    
    // empty std::list
    std::list<int> mylist;
    mylist.insert(mylist.begin(), nums.begin(), nums.end());
    printstdlist("std::list mylist", mylist);
    std::list<int>::iterator listiter = mylist.begin();
    cout << "before insert cur iterator:" << *listiter << endl;
    mylist.insert(listiter, -10);
    // 在listiter插入n个value，listiter不会发生改变
    mylist.insert(listiter, 3, -200);
    printstdlist("std::list after insert", mylist);
    cout << "after insert cur iterator not change:" << *listiter << endl;
    listiter = mylist.begin();
    cout << "cur begin iterator:" << *listiter << endl;
    // access back or front element
    cout << "back() last element:" << mylist.back() << endl;
    cout << "front() first element:" << mylist.front() << endl;
    
    string str;
    str.push_back('(');
    str.pop_back();
}

void STLExample::randomExample()
{
    /* initialize random seed: */
    // 耗时操作，只做一次随机种子处理
    srand (time(NULL));
    // [0,10) rand() % 10
    // [1,11) rand() % 10 + 1
    int num = rand() % 10 + 1;
    vector<int> nums{2,4,5,56,7,7,8,8,0};
    int size = nums.size();
    
//    for(int i=0;i<100;i++)
//    {
//        int select = nums[rand() % size];
//        cout << "random:" << select << " ";
//    }
    cout << endl;
    cout << "random num:" << num << endl;
    myshuffle(nums);
    printfVector("shuffle", nums);
}

void STLExample::stringExample()
{
    // string example
    // isalpha() 检测是否是字母
    // isdigit() 检测是否是数字
    // isalnum() 检测是否是数字或者字母
    // tolower() 转换成小写字母
    string mystring("Hello world");
    mystring.insert(0, ",,,");
    // 插入3个字符,
    mystring.insert(0, 3, ',');
    
    mystring.substr(0, 5);
    
    // 242. 有效的字母异位词(字母相同排列不同)
    // s = "anagram", t = "nagaram"
    string s = "anagram";
    string t = "nagaram";
    // isAnagram
    bool isAnagram = false;
    if(s.length() == t.length())
    {
        sort(s.begin(), s.end());
        sort(t.begin(), t.end());
        
        if(s == t)
        {
            isAnagram = true;
        }
    }
}
